package datastructure.graph.无向图;

/**
 * @author MaoLin Wang
 * @description
 * @date 2020/8/27 3:56 下午
 */
public class Cycle {
    private boolean[] marked;
    private boolean hasCycle;

    public Cycle(Graph graph) {
        marked=new boolean[graph.getV()];
        for (int i = 0; i < graph.getV(); i++) {
            if (!marked[i]){
                dfs(graph,i,i);
            }
        }
    }

    private void dfs(Graph graph, int v, int u) {
        marked[v]=true;
        for (Integer w : graph.adj(v)) {
            if (!marked[w]){
                dfs(graph,w,v);
            }else if (w!=u){
                hasCycle=true;
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addEdge(0, 2);
        graph.addEdge(2, 1);
        graph.addEdge(2, 3);
        graph.addEdge(5,4);
        Cycle cycle=new Cycle(graph);
        System.out.println(cycle.hasCycle);
    }
}
